Komplexitätstheorie
Dozent: Klaus-Jörn Lange
Zeit: Di 16-18 Uhr, Do 16-18 Uhr
Ort: siehe Aushang
Übungen (2stündig)
Inhalt der Vorlesung
Die Komplexitätstheorie klassifiziert die berechenbaren
Probleme nach der Schwierigkeit ihrer Lösbarkeit durch
Computer. Ein besonderer Augenmerk liegt dabei in der Ermittlung
von Gründen für die hartnäckige Schwierigkeit
einiger Probleme. Dieses Gebiet ist erst vor ca. 25 Jahren
ein Forschungsthema geworden, hat sich aber inzwischen enorm
ausgeweitet und umfaßt heute einen großen Bereich
der Forschungsaktivitäten in der Theoretischen Informatik.
In der Vorlesung soll ausgehend von der Betrachtung konkreter
Probleme der theoretische Rahmen für das Verständnis
einiger komplexitätstheoretischer Kernresultate erarbeitet
werden. Die folgenden Stichworte deuten den etwaigen Aufbau der
Vorlesung an: sequentielle Berechnungsmodelle,
Komplexitätsklassen, Größter und
durchschnittlicher Betriebsmittelaufwand, die Klassen P und NP,
Komplexität von Optimierungsproblemen, das Primzahlproblem
und die Klasse UP, die Polynomielle Hierarchie,
Platzkomplexitätsklassen, Probabilistische
Komplexitätsklassen, Interaktive Beweissysteme,
Schaltkreise und parallele Modelle.
Vorraussetzungen:
Informatik III
Literatur:
Wird in der Vorlesung vorgestellt.
This page was last updated on Juli 18th, 1997 by
P. Meißner